home *** CD-ROM | disk | FTP | other *** search
/ Programmer Plus 2007 / Programmer-Plus-2007.iso / Programming / Compilers / Miracle C Compiler / miricleC compiler.msi / Instal01.cab / _9BC380D094904493B3FD1F343CC441B5 < prev    next >
Encoding:
Text File  |  1999-02-27  |  1.8 KB  |  85 lines
  1. #include <stdio.h>
  2.  
  3. int *partition(int *a,int *b,int c);
  4.  
  5. int findpivot(int *a,int *b);
  6. void qsort(int *a,int *b);
  7.  
  8. /*  Hoare's Quicksort in C  */
  9.  
  10. void main()
  11. {
  12. int count, value, items, *ptr, *data;
  13.  
  14.    printf("how many values?\n\n");
  15.    scanf("%d",&count);
  16.    ptr=data=malloc(2*count); items=count;
  17.    printf("enter values:\n\n");
  18.  
  19.    /* read values into 'data' array */
  20.  
  21.    while(count>0)
  22.       {
  23.       scanf("%d",&value);
  24.       *ptr=value;
  25.       ptr=ptr+1; count=count-1;
  26.       };
  27.  
  28.    count=items; qsort(data,data+count-1);
  29.    ptr=data; puts("sorted values");
  30.  
  31.    /* print sorted values */
  32.  
  33.    while(count>0)
  34.       {
  35.       printf("%d ",*ptr);
  36.       ptr=ptr+1; count=count-1;
  37.       };
  38. }
  39.  
  40.  
  41. void qsort(int *left,int *right)
  42. {
  43. int pivot, *k;
  44.  
  45.    pivot = findpivot(left,right);   /* find valid pivot */
  46.  
  47.    if(pivot != 0)
  48.       {
  49.       k = partition(left,right,pivot);  /* partition data into LH and RH */
  50.       qsort(left,k-1);   /* sort items < pivot */
  51.       qsort(k,right);    /* sort items >=pivot */
  52.       };
  53. }
  54.  
  55.  
  56. int findpivot(int *left, int *right)
  57. {
  58. int *s, k;
  59.  
  60. s=left; k=*s; s=s+1;
  61. while(s<=right)
  62.    {
  63.    if(*s>k) return *s;   /* return largest of first two distinct values */
  64.    if(*s<k) return k;
  65.    s=s+1;
  66.    };
  67. return 0;   /* or zero if all values are same */
  68. }
  69.  
  70.  
  71. int *partition(int *left, int *right, int pivot)
  72. {
  73. int *lcurs,*rcurs,temp;
  74.  
  75. lcurs=left; rcurs=right;  /* left, right cursors */
  76.  
  77. for(;;)
  78.    {
  79.    temp=*lcurs; *lcurs=*rcurs; *rcurs=temp;  /* swap values */
  80.    while(*lcurs<pivot)  lcurs=lcurs+1; /* incr left cursor until value>=pivot */
  81.    while(*rcurs>=pivot) rcurs=rcurs-1; /* decr right cursor until value<pivot */
  82.    if(lcurs>rcurs) return lcurs;  /* set partitioned */
  83.    };
  84. }
  85.